<!DOCTYPE html>
<html>
<head>
    

    

    



    <meta charset="utf-8">
    
    
    
    
    <title>【转载】二叉排序树和平衡二叉树详解 | 博客主页 | 世界是个球，前方总有路！</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    
    <meta name="theme-color" content="#3F51B5">
    
    
    <meta name="keywords" content="数据结构与算法">
    <meta name="description" content="一、前言&amp;emsp;&amp;emsp;这两天想学学在Java中广泛使用的数据结构——红黑树，但是看博客说学习红黑树之前需要了解二叉排序树以及平衡二叉树，所以我花了点事件把这两个数据结构学习了一遍，也自己实现了一下这两种数据结构。可以说这是两种比较复杂的数据结构，尤其是平衡二叉树。但幸运的是，我找到了两篇讲解得非常不错的博客，而我这篇博客的目的就是要向想要学习这两种数据结构的人推荐这两篇博客，顺便也是给自">
<meta property="og:type" content="article">
<meta property="og:title" content="【转载】二叉排序树和平衡二叉树详解">
<meta property="og:url" content="http://tewuyiang.gitee.io/blog/%E3%80%90%E8%BD%AC%E8%BD%BD%E3%80%91%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E5%92%8C%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E8%AF%A6%E8%A7%A3/index.html">
<meta property="og:site_name" content="博客主页">
<meta property="og:description" content="一、前言&amp;emsp;&amp;emsp;这两天想学学在Java中广泛使用的数据结构——红黑树，但是看博客说学习红黑树之前需要了解二叉排序树以及平衡二叉树，所以我花了点事件把这两个数据结构学习了一遍，也自己实现了一下这两种数据结构。可以说这是两种比较复杂的数据结构，尤其是平衡二叉树。但幸运的是，我找到了两篇讲解得非常不错的博客，而我这篇博客的目的就是要向想要学习这两种数据结构的人推荐这两篇博客，顺便也是给自">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-03-20T18:40:36.000Z">
<meta property="article:modified_time" content="2020-03-20T19:04:07.903Z">
<meta property="article:author" content="特务依昂">
<meta property="article:tag" content="数据结构与算法">
<meta name="twitter:card" content="summary">
    
        <link rel="alternate" type="application/atom+xml" title="博客主页" href="/blog/atom.xml">
    
    <link rel="shortcut icon" href="/blog/img/title.png">
    <link rel="stylesheet" href="//unpkg.com/hexo-theme-material-indigo@latest/css/style.css">
    <script>window.lazyScripts=[]</script>

    <!-- custom head -->
    

<meta name="generator" content="Hexo 4.2.0"></head>

<body>
    <div id="loading" class="active"></div>

    <aside id="menu" class="hide" >
  <div class="inner flex-row-vertical">
    <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menu-off">
        <i class="icon icon-lg icon-close"></i>
    </a>
    <div class="brand-wrap" style="background-image:url(/blog/img/brand.jpg)">
      <div class="brand">
        <a href="/blog/" class="avatar waves-effect waves-circle waves-light">
          <img src="/blog/img/avatar.jpg">
        </a>
        <hgroup class="introduce">
          <h5 class="nickname">特务依昂</h5>
          <a href="mailto:1131564805@qq.com" title="1131564805@qq.com" class="mail">1131564805@qq.com</a>
        </hgroup>
      </div>
    </div>
    <div class="scroll-wrap flex-col">
      <ul class="nav">
        
            <li class="waves-block waves-effect">
              <a href="/blog/"  >
                <i class="icon icon-lg icon-home"></i>
                主页
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/blog/archives"  >
                <i class="icon icon-lg icon-archives"></i>
                博客
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/blog/tags"  >
                <i class="icon icon-lg icon-tags"></i>
                标签
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/blog/categories"  >
                <i class="icon icon-lg icon-th-list"></i>
                分类
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://github.com/tewuyiang" target="_blank" >
                <i class="icon icon-lg icon-github"></i>
                Github
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://weibo.com/u/5516635708/" target="_blank" >
                <i class="icon icon-lg icon-weibo"></i>
                Weibo
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://www.cnblogs.com/tuyang1129/" target="_blank" >
                <i class="icon icon-lg icon-link"></i>
                博客园
              </a>
            </li>
        
      </ul>
    </div>
  </div>
</aside>

    <main id="main">
        <header class="top-header" id="header">
    <div class="flex-row">
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light on" id="menu-toggle">
          <i class="icon icon-lg icon-navicon"></i>
        </a>
        <div class="flex-col header-title ellipsis">【转载】二叉排序树和平衡二叉树详解</div>
        
        <div class="search-wrap" id="search-wrap">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
                <i class="icon icon-lg icon-chevron-left"></i>
            </a>
            <input type="text" id="key" class="search-input" autocomplete="off" placeholder="输入感兴趣的关键字">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="search">
                <i class="icon icon-lg icon-search"></i>
            </a>
        </div>
        
        
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menuShare">
            <i class="icon icon-lg icon-share-alt"></i>
        </a>
        
    </div>
</header>
<header class="content-header post-header">

    <div class="container fade-scale">
        <h1 class="title">【转载】二叉排序树和平衡二叉树详解</h1>
        <h5 class="subtitle">
            
                <time datetime="2020-03-20T18:40:36.000Z" itemprop="datePublished" class="page-time">
  2020-03-21
</time>


	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/blog/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/">数据结构与算法</a></li></ul>

            
        </h5>
    </div>

    


</header>


<div class="container body-wrap">
    
    <aside class="post-widget">
        <nav class="post-toc-wrap post-toc-shrink" id="post-toc">
            <h4>TOC</h4>
            <ol class="post-toc"><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#一、前言"><span class="post-toc-number">1.</span> <span class="post-toc-text">一、前言</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#二、正文"><span class="post-toc-number">2.</span> <span class="post-toc-text">二、正文</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#三、代码"><span class="post-toc-number">3.</span> <span class="post-toc-text">三、代码</span></a></li></ol>
        </nav>
    </aside>


<article id="post-【转载】二叉排序树和平衡二叉树详解"
  class="post-article article-type-post fade" itemprop="blogPost">

    <div class="post-card">
        <h1 class="post-card-title">【转载】二叉排序树和平衡二叉树详解</h1>
        <div class="post-meta">
            <time class="post-time" title="2020-03-21 02:40:36" datetime="2020-03-20T18:40:36.000Z"  itemprop="datePublished">2020-03-21</time>

            
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/blog/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/">数据结构与算法</a></li></ul>



            
<span id="busuanzi_container_page_pv" title="文章总阅读量" style='display:none'>
    <i class="icon icon-eye icon-pr"></i><span id="busuanzi_value_page_pv"></span>
</span>


        </div>
        <div class="post-content" id="post-content" itemprop="postContent">
            <h2 id="一、前言"><a href="#一、前言" class="headerlink" title="一、前言"></a>一、前言</h2><p>&emsp;&emsp;这两天想学学在<code>Java</code>中广泛使用的数据结构——红黑树，但是看博客说学习红黑树之前需要了解<strong>二叉排序树</strong>以及<strong>平衡二叉树</strong>，所以我花了点事件把这两个数据结构学习了一遍，也自己实现了一下这两种数据结构。可以说这是两种比较复杂的数据结构，尤其是平衡二叉树。但幸运的是，我找到了两篇讲解得非常不错的博客，而我这篇博客的目的就是要向想要学习这两种数据结构的人推荐这两篇博客，顺便也是给自己做个标记，方便之后再次阅读。</p>
<br>

<h2 id="二、正文"><a href="#二、正文" class="headerlink" title="二、正文"></a>二、正文</h2><p>&emsp;&emsp;首先附上这两篇博客的链接：</p>
<ul>
<li><a href="https://www.jianshu.com/p/ff4b93b088eb" target="_blank" rel="noopener">数据结构（二）：二叉搜索树（Binary Search Tree）</a></li>
<li><a href="https://www.jianshu.com/p/655d83f9ba7b" target="_blank" rel="noopener">数据结构（四）：平衡二叉树（AVL树）</a></li>
</ul>
<p>&emsp;&emsp;这两篇博客对这两种数据结构讲解的非常的清晰，尤其是第二篇平衡而叉树，感觉真的是完全讲到了点上。为了学习平衡二叉树，我上网搜了很多博客，但是讲解的都不太清楚，尤其是大部分博客所举得例子都不具备普遍性，而上面这篇博客却是一针见血。最最重要的一点是，这两篇博客的代码写的太好了，对于这两种数据结构的实现非常精炼，感觉就是用最简便的方式将它们实现了出来。而且<strong>这两篇博客是同一个作者写的，平衡二叉树是二叉搜索树的升级版，而第二篇博客的代码就是在第一篇的基础上修改而来，只要看懂了第一篇的代码，第二篇的也会更容易理解</strong>。</p>
<br>

<h2 id="三、代码"><a href="#三、代码" class="headerlink" title="三、代码"></a>三、代码</h2><p>&emsp;&emsp;上面两篇博客的代码是<code>python</code>写的，我参照着用<code>Java</code>写了一遍，不会<code>python</code>的也可以参考一下<code>Java</code>代码，逻辑是一样的（代码太长建议复制到编译器中再看）。</p>
<p><strong>（1）二叉排序树</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 实现二叉排序树（二叉搜索树）</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">BinarySearchTree</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> TreeNode root;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 树节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">TreeNode</span> </span>&#123;</span><br><span class="line">        <span class="keyword">private</span> <span class="keyword">int</span> value;</span><br><span class="line">        <span class="keyword">private</span> TreeNode lchild;</span><br><span class="line">        <span class="keyword">private</span> TreeNode rchild;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">TreeNode</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.value = value;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">TreeNode</span><span class="params">(<span class="keyword">int</span> value, TreeNode lchild, TreeNode rchild)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.value = value;</span><br><span class="line">            <span class="keyword">this</span>.lchild = lchild;</span><br><span class="line">            <span class="keyword">this</span>.rchild = rchild;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">traversal</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        traversal(root);</span><br><span class="line">        System.out.println();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 中序遍历</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> root</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">traversal</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        traversal(root.lchild);</span><br><span class="line">        System.out.print(root.value + <span class="string">" "</span>);</span><br><span class="line">        traversal(root.rchild);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 插入数据</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">insert</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        root = insert(root, value);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> TreeNode <span class="title">insert</span><span class="params">(TreeNode root, <span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> TreeNode(value);</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 若需要插入的节点值小于当前遍历到的节点值，则向做递归</span></span><br><span class="line">        <span class="keyword">if</span> (value &lt; root.value)</span><br><span class="line">            root.lchild = insert(root.lchild, value);</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            root.rchild = insert(root.rchild, value);</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 根据节点值删除节点</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">delete</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        root = delete(root, value);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 删除值为value的节点</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> root  当前遍历到的节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value 需要删除的节点的value值</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> TreeNode <span class="title">delete</span><span class="params">(TreeNode root, <span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (value &lt; root.value)</span><br><span class="line">            root.lchild = delete(root.lchild, value);</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (value &gt; root.value)</span><br><span class="line">            root.rchild = delete(root.rchild, value);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">// 若找到需要删除的节点，则根据节点的子节点数量，判断删除的方法</span></span><br><span class="line">            <span class="comment">// 若当前节点有两个子节点，则将当前节点的左子树中最大的节点覆盖当前节点，</span></span><br><span class="line">            <span class="comment">// 然后将这个子节点删除</span></span><br><span class="line">            <span class="keyword">if</span> (root.lchild != <span class="keyword">null</span> &amp;&amp; root.rchild != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="comment">// 找到当前节点的左子树中，最大的节点</span></span><br><span class="line">                TreeNode maxChild = root.lchild;</span><br><span class="line">                <span class="keyword">while</span> (maxChild.rchild != <span class="keyword">null</span>)</span><br><span class="line">                    maxChild = maxChild.rchild;</span><br><span class="line">                <span class="comment">// 删除这个当前节点</span></span><br><span class="line">                root = delete(root, maxChild.value);</span><br><span class="line">                <span class="comment">// 将当前节点值改为最大子节点的值</span></span><br><span class="line">                root.value = maxChild.value;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">// 若需要删除的节点有0或1个直接子节点，则直接让它的子节点替换它</span></span><br><span class="line">                root = (<span class="keyword">null</span> == root.lchild ? root.rchild : root.lchild);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<br>

<p><strong>（2）平衡二叉树</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br><span class="line">230</span><br><span class="line">231</span><br><span class="line">232</span><br><span class="line">233</span><br><span class="line">234</span><br><span class="line">235</span><br><span class="line">236</span><br><span class="line">237</span><br><span class="line">238</span><br><span class="line">239</span><br><span class="line">240</span><br><span class="line">241</span><br><span class="line">242</span><br><span class="line">243</span><br><span class="line">244</span><br><span class="line">245</span><br><span class="line">246</span><br><span class="line">247</span><br><span class="line">248</span><br><span class="line">249</span><br><span class="line">250</span><br><span class="line">251</span><br><span class="line">252</span><br><span class="line">253</span><br><span class="line">254</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 平衡二叉树的Java实现</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">BalancedBinaryTree</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 树的根节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">private</span> TreeNode root;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 树节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">TreeNode</span> </span>&#123;</span><br><span class="line">        <span class="keyword">private</span> <span class="keyword">int</span> value;</span><br><span class="line">        <span class="keyword">private</span> <span class="keyword">int</span> height;</span><br><span class="line">        <span class="keyword">private</span> TreeNode lchild;</span><br><span class="line">        <span class="keyword">private</span> TreeNode rchild;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">TreeNode</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.value = value;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">TreeNode</span><span class="params">(<span class="keyword">int</span> value, <span class="keyword">int</span> height)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.value = value;</span><br><span class="line">            <span class="keyword">this</span>.height = height;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 中序遍历当前的平衡二叉树</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">traversal</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        traversal(root);</span><br><span class="line">        System.out.println();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 遍历以当前节点为根节点的平衡二叉树</span></span><br><span class="line"><span class="comment">     * 中序遍历</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> root</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">traversal</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (<span class="keyword">null</span> == root)</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line"></span><br><span class="line">        traversal(root.lchild);</span><br><span class="line">        System.out.print(root.value + <span class="string">" "</span>);</span><br><span class="line">        traversal(root.rchild);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 在平衡二叉树中新增加节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">insert</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        root = insert(root, value);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 在以当前节点为根节点的平衡二叉树中新增节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> root 当前根节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value 需要新增节点的value</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> TreeNode <span class="title">insert</span><span class="params">(TreeNode root, <span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (<span class="keyword">null</span> == root)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> TreeNode(value);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (value &lt; root.value)</span><br><span class="line">            root.lchild = insert(root.lchild, value);</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            root.rchild = insert(root.rchild, value);</span><br><span class="line">        <span class="comment">// 插入完成后判断当前节点的平衡性</span></span><br><span class="line">        <span class="keyword">return</span> checkBalance(root);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 删除节点值为value的节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value 需要删除节点的节点值</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">delete</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        root = delete(root, value);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 从根节点为root的子树中，删除节点值为value的节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> root</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> TreeNode <span class="title">delete</span><span class="params">(TreeNode root, <span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (<span class="keyword">null</span> == root)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (value &lt; root.value)</span><br><span class="line">            root.lchild = delete(root.lchild, value);</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (value &gt; root.value)</span><br><span class="line">            root.rchild = delete(root.rchild, value);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">/* 找到需要删除的节点后，判断这个节点的子节点的数量</span></span><br><span class="line"><span class="comment">               子节点数量为0，直接输出；为1，用子节点替代自己</span></span><br><span class="line"><span class="comment">               若子节点数目为2，分两种情况考虑：</span></span><br><span class="line"><span class="comment">                 1、左子树更深，则使用左子树中做大的节点替代根节点；</span></span><br><span class="line"><span class="comment">                 2、右子树更深，则使用右子树中最小的节点替代根节点；</span></span><br><span class="line"><span class="comment">             */</span></span><br><span class="line">            <span class="keyword">if</span> (<span class="keyword">null</span> != root.lchild &amp;&amp; <span class="keyword">null</span> != root.rchild) &#123;</span><br><span class="line">                TreeNode newRoot = getNewRoot(root);</span><br><span class="line">                root = delete(root, newRoot.value);</span><br><span class="line">                root.value = newRoot.value;</span><br><span class="line">            &#125; <span class="keyword">else</span></span><br><span class="line">                root = (<span class="keyword">null</span> == root.lchild ? root.rchild : root.lchild);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> checkBalance(root);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 在删除节点的操作中，若需要删除的节点右两个子节点，</span></span><br><span class="line"><span class="comment">     * 则需要找出一个节点直接替代需要深处的节点</span></span><br><span class="line"><span class="comment">     * 可以是左子树中最大的节点，也可以是右子树中最小的节点，根据左右子树的深度判断</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> root</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> TreeNode <span class="title">getNewRoot</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        TreeNode node = <span class="keyword">null</span>;</span><br><span class="line">        <span class="comment">// 左子树更深</span></span><br><span class="line">        <span class="keyword">if</span> (root.lchild.height &gt; root.rchild.height) &#123;</span><br><span class="line">            node = root.lchild;</span><br><span class="line">            <span class="keyword">while</span> (<span class="keyword">null</span> != node.rchild)</span><br><span class="line">                node = node.rchild;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            node = root.rchild;</span><br><span class="line">            <span class="keyword">while</span> (<span class="keyword">null</span> != node.lchild)</span><br><span class="line">                node = node.lchild;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> node;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 判断以当前节点为根节点的子树的平衡性</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> root 当前子树的根节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 返回根节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> TreeNode <span class="title">checkBalance</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (<span class="keyword">null</span> == root)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 根据当前节点的左右节点的高度差来判断平衡性</span></span><br><span class="line">        <span class="keyword">int</span> diff = getHeightDiff(root);</span><br><span class="line">        <span class="keyword">if</span> (diff &lt; <span class="number">2</span>)</span><br><span class="line">            updateHeight(root);</span><br><span class="line">        <span class="comment">// 失衡，左深右浅</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (diff == <span class="number">2</span>) &#123;</span><br><span class="line">            <span class="keyword">int</span> ldiff = getHeightDiff(root.lchild);</span><br><span class="line">            <span class="comment">// LL型失衡，直接右旋</span></span><br><span class="line">            <span class="keyword">if</span> (ldiff == <span class="number">1</span>) &#123;</span><br><span class="line">                root = RotateRight(root);</span><br><span class="line">            <span class="comment">// LR型失衡，将右节点左旋，在将当前节点右旋</span></span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span>(ldiff == -<span class="number">1</span>)&#123;</span><br><span class="line">                root.rchild = RotateLeft(root.rchild);</span><br><span class="line">                root = RotateLeft(root);</span><br><span class="line">            &#125; <span class="keyword">else</span></span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(<span class="string">"diff is error"</span>);</span><br><span class="line"></span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (diff == -<span class="number">2</span>) &#123;    <span class="comment">// 失衡，右深左浅</span></span><br><span class="line">            <span class="keyword">int</span> rdiff = getHeightDiff(root.rchild);</span><br><span class="line">            <span class="comment">// RR失衡，直接左旋</span></span><br><span class="line">            <span class="keyword">if</span> (rdiff == -<span class="number">1</span>)</span><br><span class="line">                root = RotateLeft(root);</span><br><span class="line">            <span class="comment">// RL失衡，先root的右节点右旋，然后root左旋</span></span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (rdiff == <span class="number">1</span>) &#123;</span><br><span class="line">                root.rchild = RotateRight(root.rchild);</span><br><span class="line">                root = RotateLeft(root);</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">        &#125; <span class="keyword">else</span></span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(<span class="string">"diff is error"</span>);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 获取当前节点的左右子树的高度差</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> root</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">getHeightDiff</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 有两个子节点</span></span><br><span class="line">        <span class="keyword">if</span> (<span class="keyword">null</span> != root.lchild &amp;&amp; <span class="keyword">null</span> != root.rchild)</span><br><span class="line">            <span class="keyword">return</span> root.lchild.height - root.rchild.height;</span><br><span class="line">        <span class="comment">// 只有左子节点</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (<span class="keyword">null</span> != root.lchild)</span><br><span class="line">            <span class="keyword">return</span> root.lchild.height + <span class="number">1</span>;</span><br><span class="line">        <span class="comment">// 只有右子节点</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (<span class="keyword">null</span> != root.rchild)</span><br><span class="line">            <span class="keyword">return</span> root.rchild.height + <span class="number">1</span>;</span><br><span class="line">        <span class="comment">// 无子节点</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 在插入或者删除节点后，更新当前节点的高度</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> root</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">updateHeight</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 有两个子节点</span></span><br><span class="line">        <span class="keyword">if</span> (<span class="keyword">null</span> != root.lchild &amp;&amp; <span class="keyword">null</span> != root.rchild)</span><br><span class="line">            root.height = Math.max( root.lchild.height, root.rchild.height ) + <span class="number">1</span>;</span><br><span class="line">            <span class="comment">// 只有左子节点</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (<span class="keyword">null</span> != root.lchild)</span><br><span class="line">            root.height = root.lchild.height + <span class="number">1</span>;</span><br><span class="line">            <span class="comment">// 只有右子节点</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (<span class="keyword">null</span> != root.rchild)</span><br><span class="line">            root.height = root.rchild.height + <span class="number">1</span>;</span><br><span class="line">        <span class="comment">// 无子节点</span></span><br><span class="line">        root.height = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 将当前节点为根的子树进行右旋</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> root</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> TreeNode <span class="title">RotateRight</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        TreeNode newRoot = root.lchild;</span><br><span class="line">        root.lchild = newRoot.rchild;</span><br><span class="line">        newRoot.rchild = root;</span><br><span class="line">        updateHeight(root);</span><br><span class="line">        updateHeight(newRoot);</span><br><span class="line">        <span class="keyword">return</span> newRoot;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 将当前节点为根的子树进行左旋</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> root</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> TreeNode <span class="title">RotateLeft</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        TreeNode newRoot = root.rchild;</span><br><span class="line">        root.rchild = newRoot.lchild;</span><br><span class="line">        newRoot.lchild = root;</span><br><span class="line">        updateHeight(root);</span><br><span class="line">        updateHeight(newRoot);</span><br><span class="line">        <span class="keyword">return</span> newRoot;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
        </div>

        <blockquote class="post-copyright">
    
    <div class="content">
        
<span class="post-time">
    最后更新时间：<time datetime="2020-03-20T19:04:07.903Z" itemprop="dateUpdated">2020-03-21 03:04:07</time>
</span><br>


        
        世界是个球，前方总有路！
        
    </div>
    
    <footer>
        <a href="http://tewuyiang.gitee.io/blog">
            <img src="/blog/img/avatar.jpg" alt="特务依昂">
            特务依昂
        </a>
    </footer>
</blockquote>

        


        <div class="post-footer">
            
	<ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/blog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" rel="tag">数据结构与算法</a></li></ul>


            
<div class="page-share-wrap">
    

<div class="page-share" id="pageShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://tewuyiang.gitee.io/blog/%E3%80%90%E8%BD%AC%E8%BD%BD%E3%80%91%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E5%92%8C%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E8%AF%A6%E8%A7%A3/&title=《【转载】二叉排序树和平衡二叉树详解》 — 博客主页&pic=http://tewuyiang.gitee.io/blog/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://tewuyiang.gitee.io/blog/%E3%80%90%E8%BD%AC%E8%BD%BD%E3%80%91%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E5%92%8C%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E8%AF%A6%E8%A7%A3/&title=《【转载】二叉排序树和平衡二叉树详解》 — 博客主页&source=一个未来程序员的博客~~~" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://tewuyiang.gitee.io/blog/%E3%80%90%E8%BD%AC%E8%BD%BD%E3%80%91%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E5%92%8C%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E8%AF%A6%E8%A7%A3/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《【转载】二叉排序树和平衡二叉树详解》 — 博客主页&url=http://tewuyiang.gitee.io/blog/%E3%80%90%E8%BD%AC%E8%BD%BD%E3%80%91%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E5%92%8C%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E8%AF%A6%E8%A7%A3/&via=http://tewuyiang.gitee.io/blog" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://tewuyiang.gitee.io/blog/%E3%80%90%E8%BD%AC%E8%BD%BD%E3%80%91%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E5%92%8C%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E8%AF%A6%E8%A7%A3/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>



    <a href="javascript:;" id="shareFab" class="page-share-fab waves-effect waves-circle">
        <i class="icon icon-share-alt icon-lg"></i>
    </a>
</div>



        </div>
    </div>

    
<nav class="post-nav flex-row flex-justify-between">
  
    <div class="waves-block waves-effect prev">
      <a href="/blog/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F%EF%BC%881%EF%BC%89%E2%80%94%E2%80%94%E5%8D%95%E4%BE%8B%E6%A8%A1%E5%BC%8F%E8%AF%A6%E8%A7%A3/" id="post-prev" class="post-nav-link">
        <div class="tips"><i class="icon icon-angle-left icon-lg icon-pr"></i> Prev</div>
        <h4 class="title">设计模式（1）——单例模式详解</h4>
      </a>
    </div>
  

  
    <div class="waves-block waves-effect next">
      <a href="/blog/%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3Java%E6%96%B9%E6%B3%95%E9%87%8D%E8%BD%BD%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86/" id="post-next" class="post-nav-link">
        <div class="tips">Next <i class="icon icon-angle-right icon-lg icon-pl"></i></div>
        <h4 class="title">深入理解Java中方法重载的实现原理</h4>
      </a>
    </div>
  
</nav>



    




















</article>



</div>

        <footer class="footer">
    <div class="top">
        
<p>
    <span id="busuanzi_container_site_uv" style='display:none'>
        站点总访客数：<span id="busuanzi_value_site_uv"></span>
    </span>
    <span id="busuanzi_container_site_pv" style='display:none'>
        站点总访问量：<span id="busuanzi_value_site_pv"></span>
    </span>
</p>


        <p>
            
                <span><a href="/blog/atom.xml" target="_blank" class="rss" title="rss"><i class="icon icon-lg icon-rss"></i></a></span>
            
            <span>博客内容遵循 <a rel="license noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" target="_blank">知识共享 署名 - 非商业性 - 相同方式共享 4.0 国际协议</a></span>
        </p>
    </div>
    <div class="bottom">
        <p><span>特务依昂 &copy; 2015 - 2020</span>
            <span>
                
                Power by <a href="http://hexo.io/" target="_blank">Hexo</a> Theme <a href="https://github.com/yscoder/hexo-theme-indigo" target="_blank">indigo</a>
            </span>
        </p>
    </div>
</footer>

    </main>
    <div class="mask" id="mask"></div>
<a href="javascript:;" id="gotop" class="waves-effect waves-circle waves-light"><span class="icon icon-lg icon-chevron-up"></span></a>



<div class="global-share" id="globalShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://tewuyiang.gitee.io/blog/%E3%80%90%E8%BD%AC%E8%BD%BD%E3%80%91%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E5%92%8C%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E8%AF%A6%E8%A7%A3/&title=《【转载】二叉排序树和平衡二叉树详解》 — 博客主页&pic=http://tewuyiang.gitee.io/blog/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://tewuyiang.gitee.io/blog/%E3%80%90%E8%BD%AC%E8%BD%BD%E3%80%91%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E5%92%8C%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E8%AF%A6%E8%A7%A3/&title=《【转载】二叉排序树和平衡二叉树详解》 — 博客主页&source=一个未来程序员的博客~~~" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://tewuyiang.gitee.io/blog/%E3%80%90%E8%BD%AC%E8%BD%BD%E3%80%91%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E5%92%8C%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E8%AF%A6%E8%A7%A3/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《【转载】二叉排序树和平衡二叉树详解》 — 博客主页&url=http://tewuyiang.gitee.io/blog/%E3%80%90%E8%BD%AC%E8%BD%BD%E3%80%91%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E5%92%8C%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E8%AF%A6%E8%A7%A3/&via=http://tewuyiang.gitee.io/blog" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://tewuyiang.gitee.io/blog/%E3%80%90%E8%BD%AC%E8%BD%BD%E3%80%91%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91%E5%92%8C%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E8%AF%A6%E8%A7%A3/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>


<div class="page-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <p>扫一扫，分享到微信</p>
    <img src="" alt="微信分享二维码">
</div>




    <script src="//cdn.bootcss.com/node-waves/0.7.4/waves.min.js"></script>
<script>
var BLOG = { ROOT: '/blog/', SHARE: true, REWARD: false };


</script>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/main.min.js"></script>


<div class="search-panel" id="search-panel">
    <ul class="search-result" id="search-result"></ul>
</div>
<template id="search-tpl">
<li class="item">
    <a href="{path}" class="waves-block waves-effect">
        <div class="title ellipsis" title="{title}">{title}</div>
        <div class="flex-row flex-middle">
            <div class="tags ellipsis">
                {tags}
            </div>
            <time class="flex-col time">{date}</time>
        </div>
    </a>
</li>
</template>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/search.min.js" async></script>






<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>



<script>
(function() {
    var OriginTitile = document.title, titleTime;
    document.addEventListener('visibilitychange', function() {
        if (document.hidden) {
            document.title = '人呢，怎么不见了！';
            clearTimeout(titleTime);
        } else {
            document.title = '(つェ⊂)咦!欢迎回来!';
            titleTime = setTimeout(function() {
                document.title = OriginTitile;
            },2000);
        }
    });
})();
</script>



</body>
</html>
